package by2019;

/*
 * 快速排序，找到一个轴，把比轴大的数放到轴的右边，比轴小的数放到轴的左边
 * 在轴的左右两边分别再进行快速排序，一直到轴的左右两边只剩一个数，则结束排序
 */
public class 快速排序 {

	public static void main(String[] args) {
		/*
		 * int[] num = { 8, 1, 5, 3, 7,4,2,99,0,44,55,8,3,5};
		 * System.out.println("原数组："); for (int i : num) { System.out.print(i + "  "); }
		 * //Arrays.sort(num); //QuSh(num, 0, num.length-1 ); mySort(num, 0,
		 * num.length-1); System.out.println("\n排序后："); for (int i : num) {
		 * System.out.print(i + "  "); }
		 */
		
		daoS();
	}

	private static void QuSh(int[] num, int start, int end) {
		if (start > end || start == end) {
			System.out.println("退出排序");
			return;
		}
		int s = start;
		int e = end;
		int key = num[start];
		System.out.println("key= "+key);

		while (start < end) {

			while (start < end && num[end] >= key) {
				end--;
			}
			while (start < end && num[start] <= key) {
				start++;
			}

			if (start < end) {
				int tem = num[start];
				num[start] = num[end];
				num[end] = tem;
			}
			System.out.println("start= "+start+" end= "+end);
		}
		  num[s] = num[end] ; 
		  num[end] = key ;
		
		 QuSh(num,s,start-1) ; 
		 QuSh(num,end+1,e) ;
		 
	}
	
	private static void mySort(int[] num, int r, int l) {
		//退出梦境条件
		if(r>l || r==l) {
			return ;
		}
		
		int i = r ;
		int j = l ;
		int key = num[r] ;
		
		while(i<j) {
			//从后往前查找
			while(i<j && num[j]>=key) {
				j-- ;
			}
			//从前往后查找
			while(i<j && num[i]<=key) {
				i++ ;
			}
			//位置调换
			if(i<j) {
				int tem = num[i] ;
				num[i] = num[j] ;
				num[j] = tem ;
			}
		}
		//换位完成之后把key的位置移到轴的位置，key是轴的值
		num[r] = num[i] ;
		num[i] = key ;
		
		//轴的左右两边再次进行排序操作
		mySort(num, r, --i);
		mySort(num, ++j, l);
	}
	
	private static void daoS() {
		for(int i=0; i<6; i++) {
			for(int k=0; k<i; k++) {
				System.out.print(" ");
			}
			for(int j=6; j>i; j--) {
				System.out.print("+");
			}
		
			System.out.println();
		}
	}

}
